Objects may be represented in solid modelling systems using various techniques. One which is particularly suitable for representing solid objects is sometimes termed "Constructive Solid Geometry" (CSG). In accordance with this technique a three-dimensional (3-D) solid object is represented by a functional definition identifying the set of points which lie within the object. Typically, the object is defined by a Boolean function which returns a "true" if applied to a point within the object and returns a "false" otherwise. This technique contrasts with, for example, line drawing techniques where the edges and surfaces of an object are defined rather than its volume.
The functional definition of an object effectively defines the set of points which make up the object. The functional definition of a sphere, for example, defines the set of points lying within a given radius of a center point. Composite objects are defined by combining the functional definitions of basic solid objects, or "primitives", e.g. spheres, half-spaces (i.e. the space on one side of an infinite plane), infinite cylinders. The functional definition of a dumb-bell, for example, would comprise the functional definition of each of two spheres at different positions, the functional definition of an infinite cylinder whose axis passes through the centers of the spheres and the functional definitions of two planar half-spaces which truncate the cylinder at the spheres, the functional definitions of the spheres, the cylinder and the planar half-spaces being combined using a logical expression including set operators such as the set union and intersect operators (i.e. using set theory principles). Expressions can also include other combinatorial operators such as set subtracting operators to define, for example, a composite object with a cut-out or hole. In this way hollow composite objects can be defined by subtracting a smaller object from a larger one. Such composite objects are still "solid" within the meaning of this document because points in space can be tested against the expression defining the object to determine whether they are inside or outside the object.
A composite object formed from primitives is typically defined in terms of a structure which represents the logical expression defining the object and comprises a linked set of nodes (e.g. a tree structure) with the primitives being defined at first nodes (e.g. leaf nodes of the tree), operators being defined at second or intermediate nodes to identify the combinatorial operations to be performed to construct the object from the primitives and/or sub-objects defined at lower-order nodes in the structure and the composite object being defined at an appropriate one of the operator nodes (e.g. the root of the tree).
Once an object has been defined in this way, it can be evaluated in order to determine the inside and outside and thus the boundaries of the solid. In doing so, a representation of the object with respect to space (i.e. a spatial representation) will be created. The spatial representation could take various forms depending on the application. For example, the spatial representation could be in the form of an image of the surface or of the edges of the object. This is often desired if the solid modelling system forms or is part of a graphics system. However, the solid modelling system could form a robotics control system for modelling a robot and its surroundings and controlling the movement of the robot or for controlling a tool during the manufacture of an item. Alternatively, the spatial representation could be used to compute data such as mass properties of the object.
Irrespective of the details of the form of the spatial representation and the use to which it is put, it will be appreciated by those skilled in the art that a significant amount of calculation is needed in order to process a CSG definition of a complex object due to the large number of individual component primitives.
In some cases primitives which are redundant are incorporated in a CSG definition. A primitive is said to be "redundant" if the CSG definition can be rewritten without that primitive. This can come about when building blocks which comprise a group of primitives (e.g. a cube comprising six planar half-spaces), rather than the primitives themselves, are used to simplify the generation of a CSG definition. Alternatively, or in addition, primitives can become redundant during evaluation of an object if the boundaries of the primitives are co-extensive in a region of space (termed a voxel) being considered in the spatial subdivision process. For example, consider a step-like object modelled from two rectangular blocks of different sizes located side by side with a side of one of the blocks co-extensive in part with a side of the other one; each block being defined by a set of six planar half-spaces. Although the half-spaces defining the sides of the blocks are not redundant initially, they effectively cancel each other out where the sides of the cubes are co-extensive and are, therefore, redundant when considering the object solely in this region.
Much unnecessary processing has conventionally been done during the evaluation of a CSG object because primitives which are either redundant initially, or become redundant during the processing of the definition, are not recognized as such.